Понятия со словосочетанием «возможное количество»
Связанные понятия
Минимальная игровая ситуация — обусловленное правилами игры игровое состояние, реализация которого в любом случае приведёт как минимум к ещё одному действию (ходу) соперника.
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Списочное декодирование — метод декодирования кодов, исправляющих ошибки, применяемый при большом количестве ошибок. Основная идея метода заключается в том, что вместо одного кодового слова алгоритм возвращает список из возможных вариантов, один из которых является верным.
Коэффициент Бухгольца — показатель, помогающий определению мест в турнире в таких играх, как шахматы, шашки, сёги, го, рэндзю, новус и т. д. среди участников, набравших равное количество очков. В отличие от коэффициента Бергера, который применяется в круговых турнирах, коэффициент Бухгольца применяется в турнирах, проводимых по швейцарской системе.
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Вычисле́ние — математическое преобразование, позволяющее преобразовывать входящий поток информации в выходной, с отличной от первого структурой. Если смотреть с точки зрения теории информации, вычисление — это получение из входных данных нового знания.
Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям. Обобщение задачи — расставить максимальное количество взаимно не бьющих друг друга ферзей на прямоугольном поле, в частности, квадратном поле, со стороной...
Задача о потоке
минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
В прикладной математике под задачей о назначении минимального количества исполнителей понимается задача комбинаторной оптимизации, обобщающая задачу о покрытии множества и схожая по постановке с задачей о назначениях.
Подробнее: Задача о назначении минимального количества исполнителей
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу. Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами. Последовательное...
В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).
Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход.
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Атака на основе подобранного шифротекста (англ. Chosen-ciphertext attack) — криптографическая атака, при которой криптоаналитик собирает информацию о шифре путём подбора зашифрованного текста и получения его расшифровки при неизвестном ключе. Как правило, криптоаналитик может воспользоваться устройством расшифрования один или несколько раз для получения шифротекста в расшифрованном виде. Используя полученные данные, он может попытаться восстановить секретный ключ для расшифровки. Существуют шифры...
SJN (англ. shortest job next — следующий с кратчайшим заданием) — невытесняющий алгоритм, в котором наивысший приоритет имеет самый короткий процесс.
Подробнее: Кратчайшая работа следующей
Характеристическая кривая задания (ХКЗ) - это график функции, который показывает вероятность выполнения определенного задания теста людьми с разными уровнями способностей.
Процент отражённых бросков (англ. Save percentage, принятые сокращения %ОБ, SVP, SV%, SVS%, PCT) — качественный показатель мастерства хоккейного вратаря, отображает в процентном виде отношение количества отбитых бросков (сэйвов) к общему количеству бросков за определенный временной отрезок (период, матч, неделя, месяц, сезон). Общим количеством бросков является количество моментов, при котором шайба имела возможность поразить ворота. Пятипроцентная разница в данном вратарском показателе (к примеру...
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Целочисленная сортировка — это задача сортировки коллекции значений данных при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений...
Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так...
В криптографии 'время атаки (англ. Time attack) — это атака по сторонним каналам, в которой атакующий пытается скомпрометировать криптосистему с помощью анализа времени, затрачиваемого на исполнение криптографических алгоритмов. Каждая логическая операция требует времени на исполнение на компьютере, и это время может различаться в зависимости от входных данных. Располагая точными измерениями времени для разных операций, атакующий может восстановить входные данные.
Подробнее: Атака по времени
Алгоритм маркерной корзины (англ. Token Bucket Algorithm) — алгоритм, позволяющий ограничить полосу пропускания канала и в то же время гарантировать некоторую скорость передачи данных (кадров или пакетов). Поскольку скорость передачи пакета по каналу всегда равна скорости передачи битового потока по среде передачи (или скорости модуляции), то для ограничения, или другими словами, уменьшения средней скорости передачи нужно увеличить временные интервалы между пакетами. Ограничение скорости достигается...
Алгоритм Марзулло — это алгоритм согласования данных, использующийся для выбора более точных источников для оценки точного времени из ряда источников времени, разной степени точности и усреднения времени, полученными от разных NTP-серверов. Переработанная версия этого алгоритма, названная «алгоритмом пересечений», является частью сетевого протокола для синхронизации времени (NTP).
Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения...
Алгоритм Лу́на (англ. Luhn algorithm) — алгоритм вычисления контрольной цифры номера пластиковой карты в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, а предназначен в первую очередь для выявления ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности...
Ничья́ — результат в матче или партии, при котором победитель игры или состязания не выявлен.
Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это...
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.
Ме́тод обра́тного преобразова́ния (Преобразование Н. В. Смирнова) — способ генерации случайных величин с заданной функцией распределения, путём модификации работы генератора равномерно распределённых чисел.
Округление — замена числа на его приближённое значение (с определённой точностью), записанное с меньшим количеством значащих цифр. Модуль разности между заменяемым и заменяющим числом называется ошибкой округления.
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной...
Слегка́ избы́точное число́, или квазисоверше́нное число́ (от лат. quas(i) «наподобие», «нечто вроде») — избыточное число, сумма собственных делителей которого на единицу больше самого числа.
Мнимая точность, также ложная, кажущаяся, избыточная то́чность (англ. spurious accuracy) — ошибка мнения о точности данных, возникающая на основании представления данных в более точном виде, чем известно об их точности.
Радужная таблица (англ. rainbow table) — специальный вариант таблиц поиска (англ. lookup table) для обращения криптографических хеш-функций, использующий механизм разумного компромисса между временем поиска по таблице и занимаемой памятью (англ. time-memory tradeoff). Радужные таблицы используются для вскрытия паролей, преобразованных при помощи сложнообратимой хеш-функции, а также для атак на симметричные шифры на основе известного открытого текста. Использование функции формирования ключа с применением...
Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. Обозначается одним из следующих способов...
Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Кегельба́н (от немецкого Kegelbahn — кегельная дорожка). Суть заключается в катании шаров по специальной дорожке с целью сбить установленные в виде ромба 9 кеглей.
Результативность (англ. effectiveness, синоним — эффективность) — отношение фактического результата (измеряемого показателя — т. н. «критерия результативности») к плановому.
Варианты правил го — различные своды правил настольной игры го. Отличаются отдельными деталями, трактовкой некоторых редко встречающихся в реальных партиях позиций, правилами определения результата в спорных случаях и порядком подсчёта разности очков. Все используемые на практике варианты эквиваленты в абсолютном большинстве случаев, их различия проявляются только в редких ситуациях.